package 二叉树;

import 二叉树.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * @author ycc
 * @date 2024/7/18
 */
public class BinarySearchTree<E> implements BinaryTreeInfo {
    private int size;
    private Node<E> root;
    private Comparator<E> comparator;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    /**
     * 获取二叉树的大小
     * @return
     */
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空所有元素
     */
    public void clear() {
        root = null;
        size = 0;
    }
    /**
     * 添加元素
     * @param element
     */
    public void add(E element) {
        elementNotNullCheck(element);

        // 添加第一个节点
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }

        // 添加的不是第一个节点
        // 找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        do {
            cmp = compare(element, node.getElement());
            parent = node;
            if (cmp > 0) {
                node = node.getRight();
            } else if (cmp < 0) {
                node = node.getLeft();
            } else { // 相等
                node.setElement(element);
                return;
            }
        } while (node != null);

        // 看看插入到父节点的哪个位置
        Node<E> newNode = new Node<>(element, parent);
        if (cmp > 0) {
            parent.setRight(newNode);
        } else {
            parent.setLeft(newNode);
        }
        size++;
    }

    /**
     * 删除元素
     * @param element
     */
    public void remove(E element) {

    }

    /**
     * 是否包含某元素
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return false;
    }

    /**
     * 元素不能为null
     * @param element
     */
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
    /**
     * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
     */
    private int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>)e1).compareTo(e2);
    }

    @Override
    public Object root() {
        return root;
    }
    @Override
    public Object left(Object node) {
        return ((Node<E>)node).getLeft();
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).getRight();
    }

    @Override
    public Object string(Object node) {
//        Node<E> myNode = (Node<E>)node;
//        String parentString = "null";
//        if (myNode.getParent() != null) {
//            parentString = myNode.getParent().getElement().toString();
//        }
//        return myNode.getElement() + "_p(" + parentString + ")";
        return ((Node<E>)node).getElement().toString();
    }

    /**
     * 获取某节点的前驱
     * @param node
     * @return
     * 有三种情况，代码可整合为2类
     */
    public Node<E> prveNode(Node<E> node) {
//        node = node.getLeft();
        node = node.getRight();

        // node是根节点, node属于左子树
        if(compare(node.getElement(), root.getElement()) <= 0) {
            if(node.getLeft() != null) {
                node = node.getLeft();
                while(node.getRight() != null) {
                    node = node.getRight();
                }
            }
        } else {
            // node属于右子树
            while(node.getLeft() != null) {
                node = node.getLeft();
            }
        }

        System.out.println("-----测试获取前驱----");
        if(node != null) {
            System.out.println(node.getElement());
        } else {
            System.out.println("node is null");
        }
        return node;
    }

    /**
     * 获取某节点的后继
     * @param node
     * @return
     * 有三种情况，代码可整合为2类
     */
    public Node<E> nextNode(Node<E> node) {
//        node = node.getLeft();
        node = node.getRight().getLeft();

        // node是根节点, node属于右子树
        if(compare(node.getElement(), root.getElement()) >= 0) {
            if(node.getRight() != null) {
                node = node.getRight();
                while(node.getLeft() != null) {
                    node = node.getLeft();
                }
            }
        } else {
            // node属于左子树
            while(node.getRight() != null) {
                node = node.getRight();
            }
        }

        System.out.println("-----测试获取前驱----");
        if(node != null) {
            System.out.println(node.getElement());
        } else {
            System.out.println("node is null");
        }
        return node;
    }

}
